package zuo.from0516.other.day02;

/**
 * Q25：K个一组翻转链表（困难）
 * 给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。
 * k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，
 * 那么请将最后剩余的节点保持原有顺序。
 * 你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
 */
public class Code05_ReverseNodesInKGroup {

    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode start = head;
        ListNode end = getKGroupEnd(head, k);
        if (end == null){
            return head;
        }
        reverse(start, end);
        head = end;
        ListNode lastEnd = start;
        while(lastEnd.next != null){
            start =  lastEnd.next;
            end = getKGroupEnd(start, k);
            if (end == null){
                return head;
            }
            reverse(start, end);
            lastEnd.next  = end;
            lastEnd = start;
        }
        return head;
    }

    public ListNode getKGroupEnd(ListNode start, int k){
        while(--k != 0 && start != null){
            start = start.next;
        }
        return start;
    }

    public static void reverse(ListNode start, ListNode end){
        end = end.next;
        ListNode cur = start;
        ListNode pre= null;
        ListNode next = null;
        while(cur != end){
            next  = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        start.next = end;
    }

    public static void main(String[] args) {
        ListNode end = new ListNode(2,null);
        ListNode start = new ListNode(1,end);
        reverse(start,end);
        System.out.println(end.val);

    }
}
